

// 暴力解法, 超时了
; (function () {
    return
    const { MenuItem } = require("electron");

    /**
     * @param {number[]} nums
     * @return {number}
     */
    var maxSubArray = function (nums) {
        let num = Number.MIN_SAFE_INTEGER
        if (nums.length === 1) {
            return nums[0]
        }
        nums.forEach((item, index) => {
            let ans = 0
            for (let i = index; i < nums.length; i++) {
                const val = nums[i];
                ans += val;
                num = Math.max(ans, num)
            }
        })
        return num
    };
    maxSubArray([-2, 1])
})();


// ===========错误的=============
// 用曲线图来进行解题
// 这个解法的错误, 是考虑向上的趋势,遇到向下就舍弃之前的向上.
// 如果遇到小的波动,其实不影响整体向上的
; (function () {
    return
    const { MenuItem } = require("electron");

    /**
     * @param {number[]} nums
     * @return {number}
     */
    var maxSubArray = function (nums) {
        if (nums.length === 0) return nums[0]
        let arr = [nums[0]]

        nums.forEach((item, index) => {
            if (index == 0) return
            let num = arr[index - 1] + item
            arr.push(num)
        })
        console.log(arr);
        // return
        arr.unshift(0)
        let left = null
        let delta = 0
        for (let i = 0; i < arr.length; i++) {
            console.log(arr[i]);
            if (arr[i + 1] == undefined) {
                // 当前的i是最后一个了
                if (left != null) {
                    delta = Math.max(delta, arr[i] - left)
                }
            }
            // 相等的时候不做处理
            if (arr[i] == arr[i + 1]) continue
            if (arr[i] < arr[i + 1]) {
                // 这里是上破路,当前的i可能是一个低点
                if (left == null) {
                    left = arr[i]
                }
            } else {
                // 这是下坡路, 那么当前的i可能是一个顶点
                if (left != null) {

                    delta = Math.max(delta, arr[i] - left)
                    left = null

                }
            }
        }

        console.log('最后的', delta);

    };
    // maxSubArray([1, 2,0,0,0 -3, 4])
    maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])

    // maxSubArray([-2, 1])
})();


// 新解法,是用左指针记录左边最低点,然后右指针记录每次最高点,
// 每次到最高点都记录一下.差值

// 当遇到比当前left还低时,说明后面有差值也是由新的left为最新左指针
; (function () {
    //return
    const { MenuItem } = require("electron");

    /**
     * @param {number[]} nums
     * @return {number}
     */
    var maxSubArray = function (nums) {
        if (nums.length === 1) return nums[0]
        let arr = [nums[0]]
        let max = [nums[0]]

        nums.forEach((item, index) => {
            if (index == 0) return
            let num = arr[index - 1] + item
            max = Math.max(max, item)
            arr.push(num)
        })
        // return
        arr.unshift(0)
        let left = null
        let delta = 0
        for (let i = 0; i < arr.length; i++) {
            // 当前的i是最后一个了
            if (arr[i + 1] == undefined) {

                // 最后一个left还是null,说明之前一直是下坡路或者是0,全是小于等于<=0
                // 只能在负数里面挑大个
                if (left == null) return max
                delta = Math.max(delta, arr[i] - left)
                continue

            }
            // 相等的时候不做处理
            if (arr[i] == arr[i + 1]) continue
            if (arr[i] < arr[i + 1]) {
                // 这里是上破路,当前的i可能是一个低点

                // 第一次的低点先赋值
                if (left == null) {
                    left = arr[i]
                    continue
                }


                // 不是第一次低点, 比较谁最低
                left = Math.min(left, arr[i])
            } else {
                // 这是下坡路, 那么当前的i可能是一个顶点
                //    所以计算一次与之前最低点的差值
                delta = Math.max(delta, arr[i] - left)

            }
        }

        return delta


    };
    let a = maxSubArray([-2, -1])
    console.log(a);
    // maxSubArray([-2,1,-3,4,-1,2,1,-5,4])

    // maxSubArray([-2, 1])
})();


// 利用贪心策略, 只记录正数起始的序列. 并比对
; (function () {
    //return
    /**
   * @param {number[]} nums
   * @return {number}
   */
    var maxSubArray = function (nums) {
        if (nums.length === 1) return nums[0]
        let maxNegative = -10 * 10000
        let count = 0
        let result = 0
        for (let index = 0; index < nums.length; index++) {
            const num = nums[index];
            // 这个是防止数组中的所有数字都是<=0的整数
            maxNegative = Math.max(num, maxNegative)

            // 当累加的数小于0时, 就可以终止了
            if ((count + num) < 0) {
                count = 0
                continue
            } else {
                count = count + num
                result = Math.max(result, count)
            }

        }

        if (maxNegative <= 0) return maxNegative

        return result
    };
})();





